package test.day07;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class ReOrderList {
	public static class ListNode {
		int val;
		ListNode next;
		ListNode() {}
		ListNode(int val) { this.val = val; }
		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}
	public void reorderList(ListNode head) {
		// 使用双端队列的方法来解决
		Deque<ListNode> de = new LinkedList<>();
		// 这里是取head的下一个节点，head不需要再入队了，避免造成重复
		ListNode cur = head.next;
		while (cur != null){
			de.offer(cur);
			cur = cur.next;
		}
		// 回到头部
		cur = head;
		int count = 0;
		while (!de.isEmpty()){
			if (count % 2 == 0){
				// 偶数，取出队列右边尾部的值
				cur.next = de.pollLast();
			} else {
				// 奇数，取出队列左边头部的值
				cur.next = de.poll();
			}
			cur = cur.next;
			count++;
		}
		cur.next = null;
	}

	public static void reorderListDoublePointer(ListNode head) {
		// 双指针的做法
		ListNode cur = head;
		// ArrayList底层是数组，可以使用下标随机访问
		List<ListNode> list = new ArrayList<>();
		while (cur != null){
			list.add(cur);
			cur = cur.next;
		}
		// 重新回到头部
		cur = head;
		// 注意左边是从1开始
		int l = 1, r = list.size() - 1;
		int count = 0;
		while (l <= r){
			if (count % 2 == 0){
				// 偶数
				cur.next = list.get(r);
				r--;
			} else {
				// 奇数
				cur.next = list.get(l);
				l++;
			}
			// 每一次指针都需要移动
			cur = cur.next;
			count++;
		}
		// 当是偶数的话，需要做额外处理
		if (list.size() % 2 == 0){
			cur.next = list.get(l);
			cur = cur.next;
		}

		// 注意结尾要结束一波
		cur.next = null;
	}


	public static void main(String[] args) {
		ListNode listNode1 = new ListNode(1);
		ListNode listNode2 = new ListNode(2);
		ListNode listNode3 = new ListNode(3);
		ListNode listNode4 = new ListNode(4);
		listNode1.next = listNode2;
		listNode2.next = listNode3;
		listNode3.next = listNode4;
		reorderListDoublePointer(listNode1);
	}
}
